package leetcode_day._2022._202201._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/17 9:28
 * 统计元音字母序列的数目
 * 算法：动态规划
 * 使用数组存储 n 个数中，以 a、e、i、o 和 u 结尾字母序列的个数
 */
public class _17_1220 {
    public static void main(String[] args) {
        System.out.println(new _17_1220().countVowelPermutation(144));
    }

    static int mod = (int) 1e9 + 7;
    public int countVowelPermutation(int n) {
        long a = 1, e = 1, i = 1, o = 1, u = 1;
        for (int k = 1; k < n; k++) {
            long aa = (e + i + u) % mod;
            long ee = (a + i) % mod;
            long ii = (e + o) % mod;
            long oo = i % mod;
            long uu = (i + o) % mod;
            a = aa;
            e = ee;
            i = ii;
            o = oo;
            u = uu;
        }
        return (int) ((a + e + i + o + u) % mod);
    }

}
